package com.algorithms.graphs;

import com.algorithms.linkedlists.LinkedQueue;
import com.algorithms.linkedlists.LinkedStack;
import com.algorithms.utils.AlgorithmException;

public class Graph {
	public final int MAX_VERTS = 20;
	public final int INVALID_VERT_IDX = -1;
	
	private Vertex[] vertexList;
	private int nVertices;
	private int[][] adjMatrix;

	// linked stack was used to ignore the size of stack
	// size of stack can be varied.
	private LinkedStack<Integer> stack = new LinkedStack<Integer>();
	
	// linked queue was used to ignore the size of queue
	// size of queue can be varied
	private LinkedQueue<Integer> queue = new LinkedQueue<Integer>();
	
	public Graph(){
		vertexList = new Vertex[MAX_VERTS];
		adjMatrix = new int[MAX_VERTS][MAX_VERTS];
		nVertices = 0;
		
		// initialize the adjacent matrix
		for (int i = 0; i < MAX_VERTS; i++){
			for (int j = 0; j < MAX_VERTS; j++){
				adjMatrix[i][j] = 0;
			}
		}
	}
	
	/**
	 * add 1 vertex into the graph
	 * 
	 * @param label
	 * @return
	 */
	public boolean addVertex(char label){
		if (nVertices >= MAX_VERTS){
			return false;
		}
		vertexList[nVertices++] = new Vertex(label);
		return true;
	}
	
	/**
	 * add an edge into the graph
	 * 
	 * @param start
	 * @param end
	 * @return
	 */
	public boolean addEdge(int start, int end){
		adjMatrix[start][end] = 1;
		adjMatrix[end][start] = 1;
		return true;
	}
	
	/**
	 * print out information of a vertex
	 * 
	 * @param v
	 */
	public void displayVertex(int v){
		System.out.print(vertexList[v].getLabel());
	}
	
	/**
	 * minimum spanning tree
	 */
	public void mst() throws AlgorithmException {
		// start searching from vertex index 0
		vertexList[0].setWasVisited(true);
		stack.push(0);
		
		// travel through all adjacent vertices
		// until the stack is empty
		int currV;
		while (!stack.isEmpty()){
			currV = stack.peak();
			int adjV = getAdjUnvisitedVertex(currV);
			if (adjV == INVALID_VERT_IDX){
				stack.pop();
			}else{
				vertexList[adjV].setWasVisited(true);
				stack.push(adjV);
				
				displayVertex(currV);
				displayVertex(adjV);
				System.out.print(" ");
			}
		}
		
		// when stack is empty, reset the visit list
		for (int i = 0; i < nVertices; i++){
			vertexList[i].setWasVisited(false);
		}
	}
	
	/**
	 * breadth-first search
	 * 
	 * @throws AlgorithmException
	 */
	public void bfs() throws AlgorithmException {
		// start searching from vertex index 0
		vertexList[0].setWasVisited(true);
		displayVertex(0);
		queue.push(0);
		
		int v1, v2;
		while (!queue.isEmpty()){
			v1 = queue.pop();
			while ((v2 = getAdjUnvisitedVertex(v1)) != INVALID_VERT_IDX){
				vertexList[v2].setWasVisited(true);
				queue.push(v2);
				displayVertex(v2);
			}
		}
		
		// when queue is empty, reset the visit list
		for (int i = 0; i < nVertices; i++){
			vertexList[i].setWasVisited(false);
		}
	}
	
	/**
	 * depth-first search
	 */
	public void dfs() throws AlgorithmException {
		// start searching from vertex index 0
		vertexList[0].setWasVisited(true);
		displayVertex(0);
		stack.push(0);
		
		// travel through all adjacent vertices
		// until the stack is empty
		while (!stack.isEmpty()){
			int adjV = getAdjUnvisitedVertex(stack.peak());
			if (adjV == INVALID_VERT_IDX){
				stack.pop();
			}else{
				vertexList[adjV].setWasVisited(true);
				stack.push(adjV);
				displayVertex(adjV);
			}
		}
		
		// when stack is empty, reset the visit list
		for (int i = 0; i < nVertices; i++){
			vertexList[i].setWasVisited(false);
		}
	}
	
	/**
	 * find a adjacent vertex with current vertex which
	 * has not visited yet.
	 * 
	 * @param v
	 * @return
	 */
	private int getAdjUnvisitedVertex(int v){
		for (int i = 0; i < MAX_VERTS; i++){
			if (adjMatrix[v][i] == 1 && !vertexList[i].wasVisited()){
				
				// return first item that was found
				return i;
			}
		}
		// no vertex was found
		return INVALID_VERT_IDX;
	}
	
}
